package primary.primary0;

public class S0337打家劫舍III {

    /**
     * 100，64
     * 从下往上才行，从上往下就没办法收口了
     * 感觉挺少有从下往上的。
     * 总之，dfs也有个顺序，有的是先自己再左右，这个就是先左右后自己，用左右来决定自己。
     * 打家劫舍1要的是，以当前房子结尾的最大价值，
     * 打家劫舍3, 如果还用这种思维的话会发现有n个路径，每个路径会影响别的路径，所以必须倒着来。
     */
    class Solution {
        public int rob(TreeNode root) {
            int[] resArray = dfs(root);
            return Math.max(resArray[0], resArray[1]);
        }

        public int[] dfs(TreeNode curNode){
            if(curNode == null){
                return new int[]{0, 0};
            }
            int[] leftRes = dfs(curNode.left);
            int[] rightRes = dfs(curNode.right);
            int curStealed = leftRes[1] + rightRes[1] + curNode.val;
            // 总之就是还是分了两种情况，当前节点偷了的 和 当前节点没偷的
            // 然后每次判断当前节点 偷/不偷 的时候，需要根据左右节点 + 当前节点值 来判断最大值，也就是下面这个。
            // 也就是 左偷 + 右偷，左偷 + 右不偷，左不偷 + 右偷，左不偷 + 右不偷
            // 这里不能直接把 左不偷+右不偷 后面再 + 当前val，因为我们要的不是当前的最大值，要的是当前不偷的最大值和当前偷了的最大值，一定是两个值
            int curUnStealed = Math.max(Math.max(leftRes[0] + rightRes[0], leftRes[0] + rightRes[1]), Math.max(leftRes[1] + rightRes[0], leftRes[1] + rightRes[1]));
            // 答案是变成 int curUnSteald = Math.max(leftRes[0], leftRes[1]) + Math.max(rightRes[0], rightRes[1]);
            return new int[]{curStealed, curUnStealed};
        }
    }
    /**
     * 这么写是错的，应该他不是单向的，不能只走一条龙，而是可以全都走
     */
    class Solution0 {
        public int rob(TreeNode root) {
            dfs(root, 0, 0);
            return maxStealedVal;
        }

        private int maxStealedVal = 0;

        public void dfs(TreeNode curNode, int preStealed, int preUnStealed){
            if(curNode == null){
                return;
            }
            int curSteald = preUnStealed + curNode.val;
            int curUnStealed = Math.max(preStealed, preUnStealed);
            maxStealedVal = Math.max(maxStealedVal, Math.max(curSteald, curUnStealed));
            dfs(curNode.left, curSteald, curUnStealed);
            dfs(curNode.right, curSteald, curUnStealed);
        }
    }


    private class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }


}
